package sword.chapter5HashMap;

/**
 * 外星语言是否排序
 * 数组下标模拟哈希表的键，存储每一个字母的位置
 * 对String[]当前元素和下一元素比较顺序
 * i == word1.length();用于正序判断
 *
 * @author K
 * @date 2021/12/3 09:00
 */
public class S34IsAlienSorted {

    public static boolean s34(String[] words, String order) {
        int[] orderArray = new int[order.length()];
        for (int i = 0; i < order.length(); i++) {
            orderArray[order.charAt(i) - 'a'] = i;
        }

        for (int i = 0; i < words.length - 1; i++) {
            if (!isOrder(words[i], words[i + 1], orderArray)) {
                return false;
            }
        }
        return true;
    }

    private static boolean isOrder(String word1, String word2, int[] orderArray) {
        int i = 0;
        for (; i < word1.length() && i < word2.length(); i++) {
            int index1 = word1.charAt(i) - 'a';
            int index2 = word2.charAt(i) - 'a';
            if (orderArray[index1] < orderArray[index2]) {
                return true;
            }
            if (orderArray[index1] > orderArray[index2]) {
                return false;
            }
        }
        return i == word1.length();
    }

    public static void main(String[] args) {
        String order = "zyxwvutsrqponmlkjihgfedcba";
        String[] words = new String[]{"offer", "is", "coming"};
        boolean result = s34(words, order);
        System.out.println();
    }

}
